// https://leetcode.cn/problems/complete-binary-tree-inserter/
// Created by ade on 2022/7/25.
//

/*
 * 层序遍历
 *
 *
 * */
#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/*
 *              1
 *         2          3
 *      4     5    6
 *
 * */

class CBTInserter {
public:
    TreeNode *root;
    int count = 0;
    vector<TreeNode *> res;
    vector <vector<TreeNode *>> res2;

    CBTInserter(TreeNode *root) {
        this->root = root;
        dfs(this->root, 0);
        for (auto items:res2) {
            for (auto i : items) {
                res.push_back(i);
            }
        }
    }

    int insert(int val) {
        TreeNode *child = new TreeNode(val);
        res.push_back(child);
        count++;
        int parent = (count >> 1) - 1;
        cout << "count:" << count << ",parent:" << parent << ",parent val:" << res[parent]->val << endl;
        if (count % 2 == 1) {
            res[parent]->right = child;
        } else {
            res[parent]->left = child;
        }
        return res[parent]->val;
    }

    TreeNode *get_root() {
        return this->root;
    }

    void dfs(TreeNode *root, int index) {
        if (root) {
            if (index >= res2.size()) res2.push_back({});
            res2[index].push_back(root);
            count++;
            dfs(root->left, index + 1);
            dfs(root->right, index + 1);

        }
    }

    void show(TreeNode *root) {
        if (root) {
            cout << root->val << ",";
            show(root->left);
            show(root->right);
        }
    }
};

TreeNode *init() {
    TreeNode *n1 = new TreeNode(1);
//    TreeNode *n2 = new TreeNode(2);
//    TreeNode *n3 = new TreeNode(3);
//    TreeNode *n4 = new TreeNode(4);
//    TreeNode *n5 = new TreeNode(5);
//    TreeNode *n6 = new TreeNode(6);
//    n1->left = n2;
//    n1->right = n3;
//    n2->left = n4;
//    n2->right = n5;
//    n3->left = n6;

    return n1;
}
// 100

int main() {
    TreeNode *h1 = init();
    CBTInserter so(h1);
    so.insert(2);
    so.show(h1);
    cout << endl;
    so.insert(3);
    so.show(h1);
    cout << endl;
    so.insert(4);
    so.show(h1);
    return 0;
//    auto res = so.levelOrder(h1);
//    for (auto items : res) {
//        for (auto i : items) {
//            cout << i << ",";
//        }
//        cout << endl;
//    }
//    return 0;
}
